package a2;

import java.util.List;
import java.util.LinkedList;
import java.util.ListIterator;

/**
Instances of this class represent nodes of ordered trees where
the data in each node is of a class specified by the user.  

Parse trees, syntax trees, and other ordered trees may be represented
by their roots.

There is no upper bound on the number of children that an ordered tree
may have. 

Instances of this class are mutable only through the iterator.

@author Jeff Smith
@version for CS 152, Fall 2011, SJSU

 */
public class OrderedTree<E>
{

    // the data in the node
    private E data;
    // a list of the node's children
    private LinkedList<OrderedTree<E>> children;

    /**
    Builds an ordered tree with null data and an empty 
    list of children.
     */
    public OrderedTree()
    {
        this(null, null);
    }

    /**
    Builds an ordered tree from given data and children.
    A shallow copy is made of the list of children.
    @param data the data for the node.  Null values
    are permitted
    @param children the list of children of the node.
    Null values are converted to empty lists.
     */
    public OrderedTree(E data, List<OrderedTree<E>> children)
    {
        this.data = data;
        if (children == null)
        {
            this.children = new LinkedList<OrderedTree<E>>();
        }
        else
        {
            this.children = new LinkedList<OrderedTree<E>>(children);
        }
    }

    /**
    Finds the value of the data in the root 
    @return the value of the data in the root (which may be null)
     */
    public E getRootData()
    {
        return data;
    }

    /**
    Returns the number of children of the tree
    @return the number of children
     */
    public int getNumberOfChildren()
    {
        return children.size();
    }

    /**
    Returns the kth child of the tree.
    No copy is made of this child
    @param k the index of the child to be
    returned, starting with 1 for the first child
    @return the kth child
     */
    public OrderedTree<E> getKthChild(int k)
    {
        return children.get(k - 1);
    }

    /**
    Determines whether the ordered tree equals another ordered
    tree.  The comparison is a deep comparison that uses 
    <code>equals</code> to compare each node.  In particular,
    two trees without children are equal iff their roots are.
    @param o the other ordered tree
    @return <code>true</code> iff the two trees are equal
     */
    public boolean equals(Object o)
    {
        if (o == null)
        {
            return false;
        }
        if (getClass() != o.getClass())
        {
            return false;
        }
        OrderedTree<E> otherTree = (OrderedTree<E>) o;
        if (!data.equals(otherTree.data))
        {
            return false;
        }
        for (int k = 0; k < children.size(); k++)
        {
            if (!children.get(k).equals(otherTree.children.get(k)))
            {
                return false;
            }
        }
        return true;
    }

    /**
    Traverses the tree rooted at the node, in preorder.
    A null data value is treated as an empty string, and
    a null list of children is treated as an empty list.
    @return a string representing the result of preorder
    traversal, with the contents of every node appearing
    on a separate line, indented an amount proportional to
    its distance from the root
     */
    public String toString()
    {
        return toString("", System.getProperty("line.separator"));
    }

    /**
    A function that behaves as toString, but takes the amount
    of indentation of the first line as a parameter.
    @param indentation a string of spaces representing 
    the indentation of each child from its parent 
    @param newline the string to be used to separate lines of output
    @return a printed representation of the traversal, suitable
    as a return value for toString()
     */
    private String toString(String indentation, String newline)
    {
        StringBuffer resultSoFar =
                new StringBuffer(indentation);  // won't be null

        // print the data, appropriately indented

        if (data == null)
        {
            resultSoFar.append("null");
        }
        else
        {
            resultSoFar.append(data.toString());
        }
        resultSoFar.append(newline);

        // recursively print the children,
        //   indented an additional two spaces

        if (children == null)
        {
            return new String(resultSoFar);
        }
        ListIterator<OrderedTree<E>> lit = children.listIterator();
        while (lit.hasNext())
        {
            String childString =
                    lit.next().toString(indentation + "  ", newline);
            resultSoFar.append(childString);
        }
        return new String(resultSoFar);
    }
}